package Ch_2_1_Elementary_Sorts;

import static Tool.ArrayGenerator.*;
import edu.princeton.cs.algs4.*;

public class Practise_2_1_15 {
    private static long select = 0;
    public static void selection(int[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i + 1; j < N; j++)
                if (a[j] < a[min]) min = j;
            select++;
            int t = a[min];
            a[min] = a[i];
            a[i] = t;
        }   
    }
    private static long insert = 0;
    public static void insertion(int[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++)
            for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
                insert++;
                int t = a[j];
                a[j] = a[j - 1];
                a[j - 1] = t;
            }  
    }
    private static long shell = 0;
    public static void shell(int[] a) {
        int N = a.length, h = 1;
        while (h < N / 3) h = 3 * h + 1;
        while (h >= 1) {
            for (int i = h; i < N; i++) 
                for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
                    shell++;
                    int t = a[j];
                    a[j] = a[j - h];
                    a[j - h] = t;
                }
            h /= 3;
        }
    }
    public static void test() {
        for (int i = 100; i < 10000; i += 100) {
            int[] arr = ints(i);
            int[] copy1 = copy(arr);
            int[] copy2 = copy(arr);
            selection(arr);
            insertion(copy1);
            shell(copy2);
            long min = select < insert ? (select < shell ? select : shell) : (insert < shell ? insert : shell);
            StdOut.printf("规模 %d 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = %d : %d : %d\n", 
                    i, select / min, insert / min, shell / min);
            select = insert = shell = 0;
        }
    }
    public static void main(String[] args) {
        /*
         * 应该用选择排序，不论在任何情况下，都只需要 N 次交换
         * 当我们考虑实际问题时，交换的次数小于等于 N, 
         * 毕竟如果查找的序列中没有比假定最小的小，那么不用自己和自己交换
         * 很显然，希尔排序和插入排序的交换次数都有可能大于 N
         */
        test();
    }
    // output
    /*
     *  规模 100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 24 : 4
        规模 200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 47 : 5
        规模 300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 74 : 6
        规模 400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 97 : 7
        规模 500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 125 : 7
        规模 600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 146 : 6
        规模 700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 172 : 6
        规模 800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 204 : 7
        规模 900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 228 : 7
        规模 1000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 248 : 7
        规模 1100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 263 : 9
        规模 1200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 304 : 8
        规模 1300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 322 : 7
        规模 1400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 343 : 8
        规模 1500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 373 : 8
        规模 1600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 411 : 9
        规模 1700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 427 : 9
        规模 1800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 445 : 8
        规模 1900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 474 : 9
        规模 2000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 502 : 8
        规模 2100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 522 : 9
        规模 2200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 540 : 9
        规模 2300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 567 : 8
        规模 2400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 589 : 9
        规模 2500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 625 : 8
        规模 2600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 633 : 8
        规模 2700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 696 : 10
        规模 2800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 691 : 9
        规模 2900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 722 : 9
        规模 3000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 742 : 9
        规模 3100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 783 : 8
        规模 3200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 813 : 9
        规模 3300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 834 : 9
        规模 3400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 843 : 9
        规模 3500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 876 : 9
        规模 3600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 890 : 9
        规模 3700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 922 : 10
        规模 3800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 957 : 9
        规模 3900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 958 : 9
        规模 4000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1004 : 10
        规模 4100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1018 : 10
        规模 4200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1056 : 10
        规模 4300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1054 : 9
        规模 4400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1106 : 10
        规模 4500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1106 : 10
        规模 4600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1135 : 9
        规模 4700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1151 : 10
        规模 4800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1199 : 9
        规模 4900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1205 : 9
        规模 5000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1255 : 10
        规模 5100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1270 : 10
        规模 5200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1306 : 9
        规模 5300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1348 : 9
        规模 5400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1351 : 9
        规模 5500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1363 : 9
        规模 5600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1383 : 9
        规模 5700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1434 : 9
        规模 5800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1437 : 10
        规模 5900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1461 : 10
        规模 6000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1475 : 9
        规模 6100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1515 : 10
        规模 6200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1540 : 10
        规模 6300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1559 : 10
        规模 6400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1598 : 10
        规模 6500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1604 : 10
        规模 6600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1637 : 10
        规模 6700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1685 : 10
        规模 6800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1706 : 11
        规模 6900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1709 : 10
        规模 7000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1765 : 10
        规模 7100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1758 : 10
        规模 7200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1780 : 11
        规模 7300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1816 : 10
        规模 7400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1853 : 11
        规模 7500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1903 : 11
        规模 7600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1906 : 10
        规模 7700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1890 : 11
        规模 7800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1917 : 10
        规模 7900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1967 : 11
        规模 8000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 1983 : 11
        规模 8100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2019 : 10
        规模 8200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2047 : 10
        规模 8300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2063 : 11
        规模 8400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2099 : 12
        规模 8500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2105 : 10
        规模 8600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2153 : 12
        规模 8700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2167 : 11
        规模 8800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2184 : 11
        规模 8900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2201 : 11
        规模 9000 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2237 : 11
        规模 9100 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2268 : 10
        规模 9200 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2279 : 11
        规模 9300 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2285 : 12
        规模 9400 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2318 : 10
        规模 9500 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2357 : 11
        规模 9600 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2409 : 11
        规模 9700 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2404 : 11
        规模 9800 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2430 : 11
        规模 9900 的交换数比为 -->  选择排序 : 插入排序 : 希尔排序 = 1 : 2461 : 12
     */
}
